//输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if(head ==nullptr)
            return {};
        vector<int> res;
        ListNode* cur = head;
        while(cur)
        {
            res.push_back(cur->val);
            cur=cur->next;
        }
        reverse(res.begin(),res.end());
        return res;

    }
};

//剑指 Offer 24. 反转链表
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head)
            return nullptr;
        stack<ListNode*> st;
        ListNode* cur = head;
        while(cur)
        {
            st.push(cur);
            cur=cur->next;
        }
        ListNode* newhead = st.top();
        cur = st.top();
        st.pop();
        while(st.size())
        {   
            cur->next = st.top();
            cur=cur->next;
            st.pop();
        }
        cur->next = nullptr;
        return newhead;
        
    }
};


//剑指 Offer 18. 删除链表的节点
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(!head)
            return nullptr;
        if(head->val ==val)
        {
            ListNode* newhead = head->next;
            return newhead;
        }
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while(cur)
        {
            if(cur->val == val)
            {
                prev->next = cur->next;
                break;
            }
            prev = cur;
            cur=cur->next;
        }
        return head;
    }
};

//剑指 Offer 22. 链表中倒数第k个节点
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        stack< ListNode*> st;
        ListNode* cur =head;
        if(!cur)
            return nullptr;
        
        while(cur)
        {
            st.push(cur);
            cur=cur->next;
        }

        while(k--)
        {
            cur=st.top();
            st.pop();
        }
        return cur;
    }
};

//快慢指针
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(!head)
            return nullptr;
        ListNode* cur =head;
        ListNode* res = head;
        while(k--)
        {
            cur=cur->next;
        }
        while(cur)
        {
            cur=cur->next;
            res=res->next;
        }
        return res;
    }
};
//剑指 Offer 52. 两个链表的第一个公共节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==nullptr || headB == nullptr)
        {
            return nullptr;
        }
        int coutA = 0;
        int coutB = 0;
        ListNode* cura = headA;
        ListNode* curb = headB;
        while(cura)
        {
            coutA++;
            cura= cura->next;
        }
        while(curb)
        {
            coutB++;
            curb= curb->next;
        }
        cura = headA;
        curb = headB;
        if(coutA>coutB)
        {
            int x = coutA-coutB;
            while(x--)
            {
                cura=cura->next;
            }
        }
        else
        {
            int x = coutB-coutA;
            while(x--)
            {
                curb=curb->next;
            }
        }
        while(cura!=curb)
        {
            cura=cura->next;
            curb=curb->next;
        }
        return cura;  
    }
};



//剑指 Offer 32 - II. 从上到下打印二叉树 II
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
            queue<TreeNode*> st;
            vector<vector<int>> vv;
            vector<int> v;
            if(root==nullptr)
            {
                return {};
            }
            st.push(root);
            while(!st.empty())
            {
                int n=st.size();  //这一层有几个节点
                while(n--)
                {
                    TreeNode* cur = st.front();
                    st.pop();
                    v.push_back(cur->val);
                    if(cur->left)
                        st.push(cur->left);
                    if(cur->right)
                        st.push(cur->right);
                    
                }
                vv.push_back(v);
                v.clear();
            }
            return vv;
    }
};

//剑指 Offer 32 - III. 从上到下打印二叉树 III
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
            if(root==nullptr)
            {
                return {};
            }
            queue<TreeNode*> st;
            vector<vector<int>> vv;
            vector<int> v;
            int count = 0; //看到第几层了
            st.push(root);
            while(!st.empty())
            {
                int n=st.size();  //这一层有几个节点
                count++;
                while(n--)
                {
                    TreeNode* cur = st.front();
                    st.pop();
                    v.push_back(cur->val);
                    if(cur->left)
                        st.push(cur->left);
                    if(cur->right)
                        st.push(cur->right);
                    
                }
                if(count%2==0)
                    reverse(v.begin(),v.end());
                vv.push_back(v);
                v.clear();
            }
            return vv;
    }
};